Graphs typically include multiple nodes or vertices connected to one another by one or more edges. Graphs are useful for modeling many real world systems such as the World Wide Web and transportation systems such as highways. In particular, graphs are also useful in search engines and social networking applications.
For example, each node in the graph may represent a user account in a social networking application, and each edge in the graph may represent a social networking relationship between two user accounts (e.g., a “friend” relationship). The graph representation of the user accounts may be used to estimate the connectedness of a user account, or to determine the distance between two user accounts.
While graphs are useful, they are often very large and include a large number of edges and nodes. Such large graphs utilize a large amount of memory for storage, and also utilize a large amount of computing resources when performing graph operations. Solutions to the problems associated with large graphs include storing and using representations of the graphs that have fewer edges, rather than the complete graph. Examples of such representations include spanners and sparsifiers. A spanner is a subgraph that can be used to estimate distances between any pairs of nodes up to a constant factor approximation. A sparsifier is a subgraph that can be used to estimate the quadratic form x′Lx (which is a generalization of graph cuts) for any vector x, where L is the Laplacian matrix representation of the graph. However, computing sparsifiers typically includes solving systems of linear equations which is also computationally expensive.